public class Solution2807 {

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        int val;
        ListNode p = head, q = head.next;
        while (q != null) {
            val = gcd(p.val, q.val);
            p.next = new ListNode(val);
            p.next.next = q;
            p = q;
            q = q.next;
        }
        return head;
    }

    public static int gcd(int a, int b) {
        int r = a % b;
        while (r != 0) {
            a = b;
            b = r;
            r = a % b;
        }
        return b;
    }
}
